﻿// ---------------------------------------------------------------------------------------------------------------------
//   Copyright (c) SRT Solutions 2009. All rights reserved.
// ---------------------------------------------------------------------------------------------------------------------
using System;

namespace SRTSolutions.Elevate
{
    using global::System;
    using global::System.Collections.Generic;
    using global::System.Linq;

#if NET_3_5
    using MyTuple=Tuple;
#else
    using MyTuple = System.Tuple;
#endif


    /// <summary>
    /// Contains extension methods on the IEnumerable interface.
    /// </summary>
    public static class EnumerableExtensions
    {
        /// <summary>
        /// Applies a choosing function to a sequence. Returns the values of the choosing function that are not None.
        /// </summary>
        /// <typeparam name="TSource">The type of the source.</typeparam>
        /// <typeparam name="TResult">The type of the result.</typeparam>
        /// <param name="source">The source.</param>
        /// <param name="chooser">The chooser.</param>
        /// <returns>a sequence matching the chooser</returns>
        public static IEnumerable<TResult> Choose<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, Option<TResult>> chooser)
        {
            if (source == null)
                throw new ArgumentNullException("source", "source is null.");
            if (chooser == null)
                throw new ArgumentNullException("chooser", "chooser is null.");

            return
                source.Select(chooser)
                .Where(option => option != Option<TResult>.None)
                .Select(option => option.Value);
        }

        /// <summary>
        /// Breaks apart an input seqnence into chunks of the given size.
        /// 
        /// If the sequence does not contain enough elements to break evenly,
        /// the last chunk will be less than the given size
        /// </summary>
        /// <typeparam name="TSource">The type of the source sequence.</typeparam>
        /// <param name="source">The source sequence.</param>
        /// <param name="chunkSize">The size of each chunk.</param>
        /// <returns>Chunks of data as sequences of lists.</returns>
        public static IEnumerable<IList<TSource>> Chunk<TSource>(this IEnumerable<TSource> source, int chunkSize)
        {
            if (source == null)
                throw new ArgumentNullException("source", "source is null.");
            if (chunkSize < 1)
                throw new ArgumentException("chunk size must be greater than 0.", "chunkSize");

            return ChunkHelper(source, enumerator => BreakOffChunk(enumerator, chunkSize));
        }

        private static IEnumerable<IList<TSource>> ChunkHelper<TSource>(IEnumerable<TSource> source, Func<IEnumerator<TSource>, IEnumerable<TSource>> chunker)
        {
            using (var enumerator = source.GetEnumerator())
            {
                var currentChunk = chunker(enumerator).ToList();

                while (currentChunk.Any())
                {
                    yield return currentChunk;
                    currentChunk = chunker(enumerator).ToList();
                }
            }
        }

        private static IEnumerable<T> BreakOffChunk<T>(IEnumerator<T> enumerator, int chunkSize)
        {
            for (int i = 0; i < chunkSize && enumerator.MoveNext(); i++)
            {
                yield return enumerator.Current;
            }
        }

        /// <summary>
        /// Breaks apart an input seqnence into chunks based on a start condition
        /// and a stop condition.
        /// </summary>
        /// <typeparam name="TSource">The type of the source sequence.</typeparam>
        /// <param name="source">The source sequence.</param>
        /// <param name="startCondition">The start condition.</param>
        /// <param name="stopCondition">The stop condition.</param>
        /// <returns>Chunks of data as sequences of lists.</returns>
        public static IEnumerable<IList<TSource>> Chunk<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> startCondition, Func<TSource, bool> stopCondition)
        {
            if (source == null)
                throw new ArgumentNullException("source", "source is null.");
            if (startCondition == null)
                throw new ArgumentNullException("startCondition", "startCondition is null.");
            if (stopCondition == null)
                throw new ArgumentNullException("stopCondition", "stopCondition is null.");

            return ChunkHelper(source, enumerator => BreakOffChunk(enumerator, startCondition, stopCondition));
        }

        private static IEnumerable<T> BreakOffChunk<T>(IEnumerator<T> enumerator, Func<T, bool> startCondition, Func<T, bool> stopCondition)
        {
            while (enumerator.MoveNext())
            {
                if (startCondition(enumerator.Current))
                {
                    yield return enumerator.Current;
                    break;
                }
            }

            while (enumerator.MoveNext() && !stopCondition(enumerator.Current))
            {
                yield return enumerator.Current;
            }
        }

        /// <summary>
        /// Compares two sequences item by item using default object comparers.
        /// </summary>
        /// <typeparam name="TSource">The type of the sequences.</typeparam>
        /// <param name="source">The source sequence.</param>
        /// <param name="second">The second sequence.</param>
        /// <returns>-1, 0, 1 if the first sequence is less than, equal to, or greater than, the right sequence</returns>
        public static int Compare<TSource>(this IEnumerable<TSource> source, IEnumerable<TSource> second)
        {
            if (source == null)
                throw new ArgumentNullException("source", "source is null.");
            if (second == null)
                throw new ArgumentNullException("second", "second is null.");

            return Compare(source, second, Comparer<TSource>.Default.Compare);
        }

        /// <summary>
        /// Compares two sequences item by item using the specified comparison function.
        /// </summary>
        /// <typeparam name="T1">The type of the first sequence.</typeparam>
        /// <typeparam name="T2">The type of the second sequence.</typeparam>
        /// <param name="source">The first sequence.</param>
        /// <param name="second">The second sequence.</param>
        /// <param name="comparer">The comparison function.</param>
        /// <returns>-1, 0, 1 if the first sequence is less than, equal to, or greater than, the right sequence</returns>
        public static int Compare<T1, T2>(this IEnumerable<T1> source, IEnumerable<T2> second, Func<T1, T2, int> comparer)
        {
            if (source == null)
                throw new ArgumentNullException("source", "source is null.");
            if (second == null)
                throw new ArgumentNullException("second", "second is null.");
            if (comparer == null)
                throw new ArgumentNullException("comparer", "comparer is null.");

            using (var enumerator1 = source.GetEnumerator())
            {
                using (var enumerator2 = second.GetEnumerator())
                {
                    while (true)
                    {
                        var oneResult = enumerator1.MoveNext();
                        var twoResult = enumerator2.MoveNext();

                        if (oneResult && twoResult)
                        {
                            var result = comparer(enumerator1.Current, enumerator2.Current);

                            if (result != 0)
                            {
                                return result;
                            }
                        }
                        else if (!oneResult && !twoResult)
                        {
                            return 0;
                        }
                        else if (!oneResult)
                        {
                            return -1;
                        }
                        else
                        {
                            return 1;
                        }
                    }
                }
            }
        }

        /// <summary>
        /// Copies the elements of the source sequence to an <see cref="T:System.Array"/>, starting at a particular <see cref="T:System.Array"/> index.
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="source">The source enumerable.</param>
        /// <param name="array">The one-dimensional <see cref="T:System.Array"/> that is the destination of the elements copied from <see cref="T:System.Collections.Generic.ICollection`1"/>. The <see cref="T:System.Array"/> must have zero-based indexing.</param>
        /// <param name="arrayIndex">The zero-based index in <paramref name="array"/> at which copying begins.</param>
        /// <exception cref="T:System.ArgumentNullException">
        /// 	<paramref name="source"/> is null.
        /// </exception>
        /// <exception cref="T:System.ArgumentNullException">
        /// 	<paramref name="array"/> is null.
        /// </exception>
        /// <exception cref="T:System.ArgumentOutOfRangeException">
        /// 	<paramref name="arrayIndex"/> is less than 0.
        /// </exception>
        /// <exception cref="T:System.ArgumentException">
        /// 	<paramref name="array"/> is multidimensional.
        /// -or-
        /// <paramref name="arrayIndex"/> is equal to or greater than the length of <paramref name="array"/>.
        /// -or-
        /// The number of elements in the source <see cref="T:System.Collections.Generic.ICollection`1"/> is greater than the available space from <paramref name="arrayIndex"/> to the end of the destination <paramref name="array"/>.
        /// -or-
        /// Type <typeparamref name="T"/> cannot be cast automatically to the type of the destination <paramref name="array"/>.
        /// </exception>
        public static void CopyTo<T>(this IEnumerable<T> source, T[] array, int arrayIndex)
        {
            if (source == null)
                throw new ArgumentNullException("source", "source is null.");
            if (array == null)
                throw new ArgumentNullException("array", "array is null.");
            if (arrayIndex < 0)
                throw new ArgumentOutOfRangeException("arrayIndex", "arrayIndex must be greater than or equal to 0.");
            if (array.Rank > 1)
                throw new ArgumentException("array cannot be multidimensional.", "array");
            if (arrayIndex >= array.Length && array.Length > 0)
                throw new ArgumentException("array index cannot be greater than or equal to the array length.", "arrayIndex");
            if (arrayIndex + source.Count() > array.Length)
                throw new ArgumentException("array cannot contain all the elements in the source sequence.", "array");

            source.ForEachWithIndex((index, value) => array[arrayIndex + index] = value);
        }

        /// <summary>
        /// Causes a side effect using each element of the source enumerable and
        /// yields the original sequence. Does not perform any actions until the
        /// sequence is iterated. For an eager evaluation, use ForEach.
        /// </summary>
        /// <typeparam name="T">The type of the source enumerable.</typeparam>
        /// <param name="source">The source sequence.</param>
        /// <param name="action">
        /// The side effect to perform for each element in the enumerable.
        /// </param>
        /// <returns>The elements of the original enumerable.</returns>
        public static IEnumerable<T> Do<T>(this IEnumerable<T> source, Action<T> action)
        {
            if (source == null)
                throw new ArgumentNullException("source", "source is null.");
            if (action == null)
                throw new ArgumentNullException("action", "action is null.");

            return DoHelper(source, action);
        }

        private static IEnumerable<T> DoHelper<T>(this IEnumerable<T> source, Action<T> action)
        {
            foreach (T element in source)
            {
                action(element);
                yield return element;
            }
        }

        /// <summary>
        /// Returns the index where the element was first found in the source enumerable.
        /// </summary>
        /// <typeparam name="TSource">The type of the source enumerable.</typeparam>
        /// <param name="source">The source sequence.</param>
        /// <param name="element">The element to return the index of.</param>
        public static int FirstIndexOf<TSource>(this IEnumerable<TSource> source, TSource element)
        {
            if (source == null)
                throw new ArgumentNullException("source");

            var index = 0;
            foreach (TSource current in source)
            {
                if (current.Equals(element))
                {
                    return index;
                }

                ++index;
            }

            throw new ArgumentException("Element was not found in input sequence.", "element");
        }

        /// <summary>
        /// Returns the index where the predicate first reteurns true in the source enumerable.
        /// </summary>
        /// <typeparam name="TSource">The type of the source enumerable.</typeparam>
        /// <param name="source">The source sequence.</param>
        /// <param name="predicate">The predicate to match on.</param>
        /// <returns>
        /// The index where the predicate first returns true in the source
        /// enumerable.
        /// </returns>
        public static int FirstIndexWhere<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
        {
            if (source == null)
                throw new ArgumentNullException("source");
            if (predicate == null)
                throw new ArgumentNullException("predicate");

            var index = 0;
            foreach (TSource current in source)
            {
                if (predicate(current))
                {
                    return index;
                }

                ++index;
            }

            throw new ArgumentException("Element was not found in input sequence.", "element");
        }

        /// <summary>
        /// Returns an enumeration of enumerations as a single sequence of values.
        /// </summary>
        /// <typeparam name="T">The type of each element.</typeparam>
        /// <param name="source">The source enumeration of enumerations.</param>
        /// <returns>a single sequence</returns>
        public static IEnumerable<T> Flatten<T>(this IEnumerable<IEnumerable<T>> source)
        {
            if (source == null)
                throw new ArgumentNullException("source", "source is null.");

            return source.SelectMany(x => x);
        }

        /// <summary>
        /// Performs an action for each element in a sequence.
        /// </summary>
        /// <typeparam name="T">The type of each element in the sequence.</typeparam>
        /// <param name="source">An IEnumerable to walk.</param>
        /// <param name="action">The action to perform.</param>
        public static void ForEach<T>(this IEnumerable<T> source, Action<T> action)
        {
            if (source == null)
                throw new ArgumentNullException("source", "source is null.");
            if (action == null)
                throw new ArgumentNullException("action", "action is null.");

            foreach (var item in source)
            {
                action(item);
            }
        }

        /// <summary>
        /// Walks two sequences simultaneously and performs an action on the pairs of values.
        /// </summary>
        /// <typeparam name="T1">The type of the first sequence.</typeparam>
        /// <typeparam name="T2">The type of the second sequence.</typeparam>
        /// <param name="source1">The type of elements the first sequence.</param>
        /// <param name="source2">The type of elements in the second sequence.</param>
        /// <param name="action">The action to perform.</param>
        public static void ForEach2<T1, T2>(this IEnumerable<T1> source1, IEnumerable<T2> source2, Action<T1, T2> action)
        {
            if (source1 == null)
                throw new ArgumentNullException("source1", "source1 is null.");
            if (source2 == null)
                throw new ArgumentNullException("source2", "source2 is null.");
            if (action == null)
                throw new ArgumentNullException("action", "action is null.");

            using (var enumerator1 = source1.GetEnumerator())
            {
                using (var enumerator2 = source2.GetEnumerator())
                {
                    while (enumerator1.MoveNext() && enumerator2.MoveNext())
                    {
                        action(enumerator1.Current, enumerator2.Current);
                    }
                }
            }
        }

        /// <summary>
        /// Performs an action on each element in a sequence using the element's index.
        /// </summary>
        /// <typeparam name="T">The type of each element in the sequence.</typeparam>
        /// <param name="source">An IEnumerable to walk.</param>
        /// <param name="action">The action to perform.</param>
        public static void ForEachWithIndex<T>(this IEnumerable<T> source, Action<int, T> action)
        {
            if (source == null)
                throw new ArgumentNullException("source", "source is null.");
            if (action == null)
                throw new ArgumentNullException("action", "action is null.");

            var index = 0;
            foreach (var item in source)
            {
                action(index, item);
                index++;
            }
        }

        /// <summary>
        /// Returns true if application of the selector returns a distinct set.
        /// </summary>
        /// <typeparam name="T">The type of each element in the sequence.</typeparam>
        /// <typeparam name="T2">The type returned by the selector.</typeparam>
        /// <param name="source">The IEnumerable to examine.</param>
        /// <param name="selector"></param>
        /// <returns>True if application of the selector returns a distinct set; otherwise, false.</returns>
        public static bool IsDistinct<T,T2>(this IEnumerable<T> source, Func<T, T2> selector)
        {
            if (source == null)
                throw new ArgumentNullException("source", "source is null.");
            if (selector == null)
                throw new ArgumentNullException("selector", "selector is null.");

            return IsDistinctHelper(source, selector);
        }

        private static bool IsDistinctHelper<T,T2>(IEnumerable<T> source, Func<T, T2> selector)
        {
            return source.GroupBy(selector).All(g => g.Count() == 1);
        }

        /// <summary>
        /// Returns true if the input sequence was empty, false otherwise.
        /// </summary>
        /// <typeparam name="TSource">The type of the source sequence.</typeparam>
        /// <param name="source">The source sequence.</param>
        /// <returns>
        /// 	<c>true</c> if the source sequence is empty; otherwise, <c>false</c>.
        /// </returns>
        [Obsolete("Use Enumerable.Any() from System.Linq instead")]
        public static bool IsEmpty<TSource>(this IEnumerable<TSource> source)
        {
            return !source.Any();
        }

        /// <summary>
        /// Returns true if the input sequence was null or empty, false otherwise. This SHOULD be the ONLY method in elevate that violates the ArgumentNullException rule on the extension method parameter.
        /// </summary>
        /// <typeparam name="TSource">The type of the source sequence.</typeparam>
        /// <param name="source">The source sequence.</param>
        /// <returns>	<c>true</c> if the source sequence is null or empty; otherwise, <c>false</c>.</returns>
        public static bool IsNullOrEmpty<TSource>(this IEnumerable<TSource> source)
        {
            if (source == null) return true;

            // Collection idea from: http://danielvaughan.org/post/IEnumerable-IsNullOrEmpty.aspx
            var collection = source as ICollection<TSource>;
            return (collection != null) ? collection.Count < 1 : !source.Any();
        }

        /// <summary>
        /// Returns true if the input sequence was null or empty, false otherwise. This SHOULD be the ONLY method in elevate that violates the ArgumentNullException rule on the extension method parameter.
        /// </summary>
        /// <typeparam name="TSource">The type of the source sequence.</typeparam>
        /// <param name="source">The source sequence.</param>
        /// <returns>	<c>true</c> if the source sequence is null or empty; otherwise, <c>false</c>.</returns>
        public static bool IsNullOrEmpty<TSource>(this ICollection<TSource> source)
        {
            if (source == null) return true;
            return source.Count < 1;
        }

        /// <summary>
        /// Selects elements by walking a sequence two elements at a time and applying a
        /// selector function. If the sequence contains only one element, no elements 
        /// are returned.
        /// </summary>
        /// <typeparam name="TSource">The type of the source sequence.</typeparam>
        /// <typeparam name="TResult">The type of the return sequence.</typeparam>
        /// <param name="source">The source sequence.</param>
        /// <param name="selector">The selector function.</param>
        /// <returns>
        /// A sequence generated by walking a sequence two elements at a time and applying
        /// a selector function.
        /// </returns>
        public static IEnumerable<TResult> Pairwise<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TSource, TResult> selector)
        {
            if (source == null)
                throw new ArgumentNullException("source", "source is null.");
            if (selector == null)
                throw new ArgumentNullException("selector", "selector is null.");

            return PairwiseHelper(source, selector);
        }

        private static IEnumerable<TResult> PairwiseHelper<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TSource, TResult> selector)
        {
            using (var enumerator = source.GetEnumerator())
            {
                if (enumerator.MoveNext())
                {
                    var left = enumerator.Current;

                    while (enumerator.MoveNext())
                    {
                        var right = enumerator.Current;
                        yield return selector(left, right);
                        left = right;
                    }
                }
            }
        }

        /// <summary>
        /// Executes an action by walking a sequence two elements at a time and applying a
        /// executor function. If the sequence contains only one element, nothing is
        /// executed.
        /// </summary>
        /// <typeparam name="TSource">The type of the source sequence.</typeparam>
        /// <param name="source">The source sequence.</param>
        /// <param name="action">The action to execute.</param>
        public static void Pairwise<TSource>(this IEnumerable<TSource> source, Action<TSource, TSource> action)
        {
            if (source == null)
                throw new ArgumentNullException("source", "source is null.");
            if (action == null)
                throw new ArgumentNullException("action", "action is null.");

            PairwiseHelper(source, action);
        }

        private static void PairwiseHelper<TSource>(this IEnumerable<TSource> source, Action<TSource, TSource> action)
        {
            using (var enumerator = source.GetEnumerator())
            {
                if (enumerator.MoveNext())
                {
                    var left = enumerator.Current;

                    while (enumerator.MoveNext())
                    {
                        var right = enumerator.Current;
                        action(left, right);
                        left = right;
                    }
                }
            }
        }

        /// <summary>
        /// Walks two sequences simultaneously and returns a sequence containing the result of applying the selector funtion.
        /// </summary>
        /// <typeparam name="TSource">The type of the first IEnumerable.</typeparam>
        /// <typeparam name="TSecond">The type of the second IEnumerable.</typeparam>
        /// <typeparam name="TResult">The type of the resulting IEnumerable.</typeparam>
        /// <param name="source">An IEnumerable to walk.</param>
        /// <param name="second">The second IEnumerable to walk.</param>
        /// <param name="selector">A selector function to map elements from the source IEnumerables to the resulting IEnumerable.</param>
        /// <returns></returns>
        /// <remarks>
        /// There has been some debate on the proper naming of this function.
        /// 
        /// In .NET 4.0, this method will be called "Zip", so we'll follow suit. In other functional, languages,
        /// however, Zip refers to a function that takes two sequences and returns a sequence of tuples
        /// that combines the elements of the two input sequences. We will also support this method, but
        /// it will be an override. Note that there is precedent for this naming in Ruby.
        /// </remarks>
        [Obsolete("This extension has been renamed to be an overload of Zip")]
        public static IEnumerable<TResult> Select2<TSource, TSecond, TResult>(this IEnumerable<TSource> source, IEnumerable<TSecond> second, Func<TSource, TSecond, TResult> selector)
        {
            return source.Zip(second, selector);
        }

        /// <summary>
        /// Applies a selection function to each element of this sequence using the element's index.
        /// </summary>
        /// <typeparam name="T">The type of each element in the sequence.</typeparam>
        /// <typeparam name="TResult">The type of the result.</typeparam>
        /// <param name="source">An IEnumerable to select elements from.</param>
        /// <param name="selector">The selector function.</param>
        /// <returns></returns>
        /// 
        [Obsolete("Use Enumerable.Select<T, int, TResult> from System.Linq instead")]
        public static IEnumerable<TResult> SelectWithIndex<T, TResult>(this IEnumerable<T> source, Func<int, T, TResult> selector)
        {
            return source.Select((value, index) => selector(index, value));
        }

        /// <summary>
        /// Returns an IList containing the elements in the sequence. The input sequence is walked to populate
        /// the returned list only when an item in the returned IList is accessed.
        /// 
        /// Note: The ENTIRE list is populated when any one item is read.
        /// </summary>
        /// <typeparam name="T">The type of each element in the sequence</typeparam>
        /// <param name="source">A sequence to convert into an IList.</param>
        /// <returns>The entire list.</returns>
        public static IList<T> ToDelayedList<T>(this IEnumerable<T> source)
        {
            return new DelayedList<T>(source);
        }

        /// <summary>
        /// Returns an IList containing the elements in the sequence. The input sequence is walked to populate
        /// the returned list only when an item in the returned IList is accessed.
        /// 
        /// Note: The ENTIRE list is populated when any one item is read.
        /// </summary>
        /// <typeparam name="T">The type of each element in the sequence</typeparam>
        /// <param name="source">A sequence to convert into an IList.</param>
        /// <param name="initialCount">The initial count of the delayed list.</param>
        /// <returns>The sequence converted to a delayed list</returns>
        public static IList<T> ToDelayedList<T>(this IEnumerable<T> source, int initialCount)
        {
            return new DelayedList<T>(source, initialCount);
        }

        /// <summary>
        /// Applies a predicate to every item in the sequence, and returns the first
        /// item that matches. If no items match, returns None.
        /// </summary>
        /// <typeparam name="TSource">The type of each value in the source seqnence</typeparam>
        /// <param name="source">The source sequence.</param>
        /// <param name="predicate">The predicate determining the item to project.</param>
        /// <returns>The first item that matches the predicate or None if no items match.</returns>
        public static Option<TSource> TryFind<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
        {
            if (source == null)
                throw new ArgumentNullException("source", "source is null.");
            if (predicate == null)
                throw new ArgumentNullException("predicate", "predicate is null.");

            return TryFindHelper<TSource>(source, predicate);
        }

        private static Option<TSource> TryFindHelper<TSource>(IEnumerable<TSource> source, Func<TSource, bool> predicate)
        {
            using (var results = source.Where(predicate).GetEnumerator())
            {
                if (results.MoveNext())
                {
                    return Option.Some(results.Current);
                }
                else
                {
                    return Option<TSource>.None;
                }
            }
        }

        /// <summary>
        /// Returns the index where the element was first found in the source enumerable or
        /// None if the element was not found.
        /// </summary>
        /// <typeparam name="TSource">The type of the source enumerable.</typeparam>
        /// <param name="source">The source sequence.</param>
        /// <param name="element">The element to return the index of.</param>
        /// <returns>
        /// The index where the element was first found in the source enumerable 
        /// or None if the element was not found.
        /// </returns>
        public static Option<int> TryFirstIndexOf<TSource>(this IEnumerable<TSource> source, TSource element)
        {
            if (source == null)
                throw new ArgumentNullException("source");

            var index = 0;
            foreach (TSource current in source)
            {
                if (current.Equals(element))
                {
                    return Option.Some(index);
                }

                ++index;
            }

            return Option<int>.None;
        }

        /// <summary>
        /// Returns the index where the predicate first reteurns true in the 
        /// source enumerable or None if it does not return true.
        /// </summary>
        /// <typeparam name="TSource">The type of the source enumerable.</typeparam>
        /// <param name="source">The source sequence.</param>
        /// <param name="predicate">The predicate to match on.</param>
        /// <returns>
        /// The index where the predicate first reteurns true in the source 
        /// enumerable or None if it does not return true.
        /// </returns>
        public static Option<int> TryFirstIndexWhere<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
        {
            if (source == null)
                throw new ArgumentNullException("source");
            if (predicate == null)
                throw new ArgumentNullException("predicate");

            var index = 0;
            foreach (TSource current in source)
            {
                if (predicate(current))
                {
                    return Option.Some(index);
                }

                ++index;
            }

            return Option<int>.None;
        }

        /// <summary>
        /// Applies a picking function to every value in the sequence and
        /// returns the first result for which the picker function returns Some.
        /// </summary>
        /// <typeparam name="TSource">The type of each value in the source seqnence.</typeparam>
        /// <typeparam name="TResult">The type of the option result.</typeparam>
        /// <param name="source">The source sequence.</param>
        /// <param name="picker">The picking function.</param>
        /// <returns>The Option containing the value, or None</returns>
        public static Option<TResult> TryPick<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, Option<TResult>> picker)
        {
            if (source == null)
                throw new ArgumentNullException("source", "source is null.");
            if (picker == null)
                throw new ArgumentNullException("picker", "picker is null.");

            var result =
                source
                .Select(picker)
                .FirstOrDefault(option => option.IsSome);

            if (result != null)
            {
                return result;
            }
            else
            {
                return Option<TResult>.None;
            }
        }


#if NET_3_5
        /// <summary>
        /// Walks two sequences simultaneously and returns a sequence containing the result of applying the selector funtion.
        /// </summary>
        /// <typeparam name="TSource">The type of the first IEnumerable.</typeparam>
        /// <typeparam name="TSecond">The type of the second IEnumerable.</typeparam>
        /// <typeparam name="TResult">The type of the resulting IEnumerable.</typeparam>
        /// <param name="source">An IEnumerable to walk.</param>
        /// <param name="second">The second IEnumerable to walk.</param>
        /// <param name="selector">A selector function to map elements from the source IEnumerables to the resulting IEnumerable.</param>
        /// <returns></returns>
        /// <remarks>
        /// There has been some debate on the proper naming of this function.
        /// 
        /// In .NET 4.0, this method will be called "Zip", so we'll follow suit. In other functional languages,
        /// Zip refers to a function that takes two sequences and returns a sequence of tuples
        /// that combines the elements of the two input sequences. We will also support this method, but
        /// it will be an override. Note that there is precedent for this naming in Ruby.
        /// </remarks>
        /// 
        public static IEnumerable<TResult> Zip<TSource, TSecond, TResult>(this IEnumerable<TSource> source, IEnumerable<TSecond> second, Func<TSource, TSecond, TResult> selector)
        {
            if (source == null)
                throw new ArgumentNullException("source", "source is null.");
            if (second == null)
                throw new ArgumentNullException("second", "second is null.");
            if (selector == null)
                throw new ArgumentNullException("selector", "selector is null.");

            return ZipHelper(source, second, selector);
        }
#endif

        private static IEnumerable<TResult> ZipHelper<TArg1, TArg2, TResult>(this IEnumerable<TArg1> first, IEnumerable<TArg2> second, Func<TArg1, TArg2, TResult> selector)
        {
            using (var enumerator1 = first.GetEnumerator())
            {
                using (var enumerator2 = second.GetEnumerator())
                {
                    while ((enumerator1.MoveNext() && enumerator2.MoveNext()))
                        yield return selector(enumerator1.Current, enumerator2.Current);
                }
            }
        }

        /// <summary>
        /// Combines two sequences into a sequence of tuples.
        /// </summary>
        /// <typeparam name="TSource">The type of each element in the source enumerable.</typeparam>
        /// <typeparam name="TSecond">The type of each element in the second enumerable.</typeparam>
        /// <param name="source">The source enumerable.</param>
        /// <param name="second">A second enumerable.</param>
        /// <returns>An enumerable of tuples containing the elements from the input sequences.</returns>
#if NET_3_5
        public static IEnumerable<Tuple<TSource, TSecond>> Zip<TSource, TSecond>(this IEnumerable<TSource> source, IEnumerable<TSecond> second)
#else
        public static IEnumerable<System.Tuple<TSource, TSecond>> Zip<TSource, TSecond>(this IEnumerable<TSource> source, IEnumerable<TSecond> second)
#endif
        {
            if (source == null)
                throw new ArgumentNullException("source", "source is null.");
            if (second == null)
                throw new ArgumentNullException("second", "second is null.");

            return ZipHelper(source, second, (x, y) => MyTuple.Create(x, y));
        }

        /// <summary>
        /// Merges two sorted sequences.
        /// </summary>
        /// <typeparam name="T">The type in the sequences</typeparam>
        /// <param name="sequence1">The first sequence.</param>
        /// <param name="sequence2">The second sequence.</param>
        /// <param name="comparer">The comparer.</param>
        /// <returns>A merged and sorted sequence</returns>
        public static IEnumerable<T> SortedMerge<T>(
            this IEnumerable<T> sequence1,
            IEnumerable<T> sequence2,
            IComparer<T> comparer)
        {
            var iter1 = sequence1.GetEnumerator();
            var iter2 = sequence2.GetEnumerator();
            bool seq2 = iter2.MoveNext();
            bool seq1 = iter1.MoveNext();

            while (seq1 && seq2)
            {
                if (comparer.Compare(iter1.Current, iter2.Current) <= 0)
                {
                    yield return iter1.Current;
                    seq1 = iter1.MoveNext();
                }
                else
                {
                    yield return iter2.Current;
                    seq2 = iter2.MoveNext();
                }
            }
            // might have some items in one of the sequences
            // remaining.
            while (seq1)
            {
                yield return iter1.Current;
                seq1 = iter1.MoveNext();
            }
            while (seq2)
            {
                yield return iter2.Current;
                seq2 = iter2.MoveNext();
            }
        }

        /// <summary>
        /// Merges two sorted sequences.
        /// </summary>
        /// <typeparam name="T">The type in the sequences</typeparam>
        /// <param name="sequence1">The first sequence.</param>
        /// <param name="sequence2">The second sequence.</param>
        /// <returns>A merged and sorted sequence</returns>
        public static IEnumerable<T> SortedMerge<T>(
            this IEnumerable<T> sequence1,
            IEnumerable<T> sequence2)
            where T : IComparable<T>
        {
            var comparer = Comparer<T>.Default;
            return SortedMerge(sequence1, sequence2, comparer);
        }

        /// <summary>
        /// Walks two sequences simultaneously and returns a sequence containing the result of applying the selector funtion.
        /// </summary>
        /// <typeparam name="TSource">The type of the first IEnumerable.</typeparam>
        /// <typeparam name="TSecond">The type of the second IEnumerable.</typeparam>
        /// <typeparam name="TThird">The type of the third IEnumerable.</typeparam>
        /// <typeparam name="TResult">The type of the resulting IEnumerable.</typeparam>
        /// <param name="source">An IEnumerable to walk.</param>
        /// <param name="second">The second IEnumerable to walk.</param>
        /// <param name="third">The third IEnumerable to walk.</param>
        /// <param name="selector">A selector function to map elements from the source IEnumerables to the resulting IEnumerable.</param>
        /// <returns></returns>
        /// <remarks>
        /// There has been some debate on the proper naming of this function.
        /// 
        /// In .NET 4.0, this method will be called "Zip", so we'll follow suit. In other functional languages,
        /// Zip refers to a function that takes two sequences and returns a sequence of tuples
        /// that combines the elements of the two input sequences. We will also support this method, but
        /// it will be an override. Note that there is precedent for this naming in Ruby.
        /// </remarks>
        public static IEnumerable<TResult> Zip<TSource, TSecond, TThird, TResult>(this IEnumerable<TSource> source, IEnumerable<TSecond> second, IEnumerable<TThird> third, Func<TSource, TSecond, TThird, TResult> selector)
        {
            if (source == null)
                throw new ArgumentNullException("source", "source is null.");
            if (second == null)
                throw new ArgumentNullException("second", "second is null.");
            if (third == null)
                throw new ArgumentNullException("third", "third is null.");
            if (selector == null)
                throw new ArgumentNullException("selector", "selector is null.");

            return ZipHelper(source, second, third, selector);
        }

        private static IEnumerable<TResult> ZipHelper<TSource, TSecond, TThird, TResult>(IEnumerable<TSource> first, IEnumerable<TSecond> second, IEnumerable<TThird> third, Func<TSource, TSecond, TThird, TResult> selector)
        {
            using (var enumerator1 = first.GetEnumerator())
            using (var enumerator2 = second.GetEnumerator())
            using (var enumerator3 = third.GetEnumerator())
            {
                while ((enumerator1.MoveNext() && enumerator2.MoveNext() && enumerator3.MoveNext()))
                {
                    yield return selector(enumerator1.Current, enumerator2.Current, enumerator3.Current);
                }
            }
        }

        /// <summary>
        /// Walks two sequences simultaneously and returns a running accumulation of their values.
        /// </summary>
        /// <typeparam name="TSource">The type of the first IEnumerable.</typeparam>
        /// <typeparam name="TResult">The type of the resulting IEnumerable.</typeparam>
        /// <param name="source">An IEnumerable to walk.</param>
        /// <param name="next">The accumulator function.</param>
        /// <param name="state">The initial state of the accumulator.</param>
        /// <returns></returns>
        public static IEnumerable<TResult> Scan<TSource, TResult>(this IEnumerable<TSource> source, Func<TResult, TSource, TResult> next, TResult state)
        {
            if (source == null) throw new ArgumentNullException("source");
            if (next == null) throw new ArgumentNullException("next");

            var result = ScanHelper(source, next, state);
            return result;
        }

        private static IEnumerable<TResult> ScanHelper<TSource, TResult>(IEnumerable<TSource> source, Func<TResult, TSource, TResult> next, TResult state)
        {
            yield return state;
            foreach (var item in source)
            {
                state = next(state, item);
                yield return state;
            }
        }
    }
}
